
public class Sort {
	public void downHeap(int a[], int k, int n) {
		  int new_elem;
		  int child;
		  new_elem = a[k];

		  while(k <= n/2) {  		
		    child = 2*k;
		    if( child < n && a[child] < a[child+1] ) 
		    child++;
		    if( new_elem >= a[child]) break; 
		    a[k] = a[child]; 	
		    k = child;
		  }
		  a[k] = new_elem;
	}
	
	void heapSort(int a[], int size) {
		  int i;
		  int temp;
		  for(i=size/2-1; i >= 0; i--) downHeap(a, i, size-1);
		  for(i=size-1; i > 0; i--) {
		    temp=a[i]; a[i]=a[0]; a[0]=temp;
		    downHeap(a, 0, i-1); 
		  }
	}
	
	public static void main(String[] args){
		int i;
		int[] a = {1,15,37,58,95,76,46,457};
		Sort m = new Sort();
		for(i=0;i<a.length;i++){System.out.print(a[i]+" ");}
		System.out.println();
		m.heapSort(a, a.length);
		
		for(i=0;i<a.length;i++){System.out.print(a[i]+" ");}

		// Скорость работы пирамидальной сортировки О(n log n).
		// Дополнительной памяти не требуется.
		
	}
}
